package lcr;

public class Test0078 {
    public static void main(String[] args) {
        Solution0078_1 solution = new Solution0078_1();
        ListNode[] lists = new ListNode[]{
                new ListNode(-8,new ListNode(-7)),
                new ListNode(-10,new ListNode(-6,new ListNode(-4))),
                new ListNode(-10,new ListNode(-9,new ListNode(-8))),
                new ListNode(-10,new ListNode(0,new ListNode(4)))
        };
        solution.mergeKLists(lists);
    }
}

class Solution0078_1 {
    ListNode[] heap;

    int tailIndex=-1;
    public ListNode mergeKLists(ListNode[] lists) {
        heap=new ListNode[lists.length];
        for (ListNode node : lists)
            offer(node);

        ListNode ans = new ListNode(),cur=ans;
        while (tailIndex>0){
            cur.next=peek();
            cur=cur.next;
        }

        System.out.println(heap);

        return ans.next;
    }


    public ListNode peek(){
        ListNode ans = heap[0];

        swap(0,tailIndex--);
        if (tailIndex<0) return ans;
        heapifyDown(0);

        if (ans.next!=null){
            offer(ans.next);
            ans.next=null;
        }
        return ans;
    }

    public void offer(ListNode node){
        if(node==null) return;
        heap[++tailIndex]=node;
        heapifyUp(tailIndex);
    }

    public void heapifyUp(int i){
        ListNode now = heap[i];
        int preIndex = getPreIndex(i);

        while (preIndex >=0&&heap[preIndex].val>now.val) {
            swap(i,preIndex);
            i=preIndex;
            preIndex = getPreIndex(i);
        }
    }

    public void heapifyDown(int i){

        while (i<tailIndex){
            ListNode listNode = heap[i];

            int temp=i;
            int leftIndex = getleftIndex(i);
            int rightIndex = getrightIndex(i);

            if (leftIndex<=tailIndex &&heap[leftIndex].val<heap[i].val) i=leftIndex;
            if (rightIndex<=tailIndex &&heap[rightIndex].val<heap[i].val) i=rightIndex;

            if (temp==i) break;
            swap(i,temp);
        }

    }

    public int getPreIndex(int index){
        return (index-1)>>1;
    }

    public int getleftIndex(int index){
        return index*2+1;
    }
    public int getrightIndex(int index){
        return index*2+2;
    }

    public void swap(int a,int b){
        ListNode temp = heap[a];
        heap[a]=heap[b];
        heap[b]=temp;
    }

}
